package string;

import java.util.HashMap;
import java.util.Map;

/**
 * 76. 最小覆盖子串
 * 给你一个字符串 s 、一个字符串 t 。
 * 返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * <p>
 * 注意：
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * <p>
 * <p>
 * 示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 * <p>
 * 示例 2：
 * 输入：s = "a", t = "a"
 * 输出："a"
 * 解释：整个字符串 s 是最小覆盖子串。
 * 示例 3:
 * <p>
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 */
public class Problem_76 {
    public static void main(String[] args) {
        System.out.println(new Problem_76().minWindow_1("ADOBECODEBANC", "ABC"));
        System.out.println(new Problem_76().minWindow_2("ADOBECODEBANC", "ABC"));
    }

    /**
     * 滑动窗口:
     * 我们在 s 上滑动窗口，通过 right 指针不断右移扩张窗口。
     * 当窗口中包含 t 所需的全部字符后，我们记录下当前窗口，并开始右移 left 指针来收缩窗口以得到更小的窗口 ( 直到窗口内无法包含t的全部字符时再右移right进行窗口扩张 )。
     * <p>
     * 如何判断当前的窗口包含 t 所需的所有字符呢？
     * 我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，
     * 再用一个哈希表动态维护窗口中所有的字符以及它们的个数，
     * 如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前窗口是「可行」的。
     * <p>
     * 具体做法:
     * 我们可以使用一个 count 用来记录窗口中包含 t 中字符的个数。
     * 当窗口扩张时，如果新加入的字符是 t 中的字符,并且这个字符加入后 此字符在窗口中出现次数小于等于 t 中这个字符的所需个数，则 count 加一。
     * 当窗口收缩时，如果移除掉的字符是 t 中的字符,并且这个字符移除掉后 此字符在窗口中出现次数小于 t 中这个字符的所需个数，此时 count 减一。
     * 当 count 等于 t 的长度时，说明窗口中已经包含了 t 中所有的字符。此时开始收缩窗口，直到窗口中不再包含 t 中的所有字符为止。
     */
    public String minWindow_1(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }

        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();

        // 记录 t 中 字符 和 字符的对应个数
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }

        String result = "";
        int count = 0; // 记录窗口中包含t中字符的个数
        int left = 0, right = 0;
        while (right < s.length()) {
            char rightC = s.charAt(right);
            sMap.put(rightC, sMap.getOrDefault(rightC, 0) + 1);

            if (tMap.containsKey(rightC) && sMap.get(rightC) <= tMap.get(rightC)) {
                count++;
            }

            while (count == t.length()) {
                if (result.isEmpty() || result.length() > right - left + 1) {
                    result = s.substring(left, right + 1);
                }
                char leftC = s.charAt(left);
                sMap.put(leftC, sMap.get(leftC) - 1);
                if (tMap.containsKey(leftC) && sMap.get(leftC) < tMap.get(leftC)) {
                    count--;
                }

                left++;
            }

            right++;
        }

        return result;
    }


    /**
     * 滑动窗口(优化):
     * 使用一个数组来代替两个哈希表，数组的下标代表字符，数组的值代表窗口内对应字符出现的次数。
     * 初始化数组时，数组的值代表 t 中对应字符需要的个数。
     * 具体做法：
     * right指针右移进行窗口扩张时，将数组中该字符的值减一，然后判断：
     * 如果此时，该字符的值大于等于0，表示此字符是t中需要的字符，count加一。
     * 当 count 等于 t 的长度时，说明窗口中已经包含了 t 中所有的字符。此时开始右移left指针收缩窗口，直到窗口中不再包含 t 中的所有字符为止。
     */
    public String minWindow_2(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }

        int[] hash = new int[128];
        // 记录 t中各个字符的出现频率
        for (int i = 0; i < t.length(); i++) {
            hash[t.charAt(i)]++;
        }

        String result = "";
        for (int right = 0, left = 0, count = 0; right < s.length(); right++) {
            hash[s.charAt(right)]--;
            if (hash[s.charAt(right)] >= 0) {
                count++;
            }
            // 通过向右移动 左边界left，来缩小窗口
            while (count == t.length() && hash[s.charAt(left)] < 0) {
                hash[s.charAt(left)]++;
                left++;
            }

            if (count == t.length() && (result.isEmpty() || result.length() > right - left + 1)) {
                result = s.substring(left, right + 1);
            }
        }
        return result;
    }

}
